package oct2013.linkednode;

import java.util.ArrayList;

public class UniqueBinarySearchTreesII {

	public ArrayList<TreeNode> generateTrees(int n) {
		return dfs(1, n);
	}

	ArrayList<TreeNode> dfs(int i, int j) {
		ArrayList<TreeNode> res = new ArrayList<TreeNode>();
		if (i > j)
			res.add(null);
		for (int k = i; k <= j; ++k) {
			ArrayList<TreeNode> l = dfs(i, k - 1);
			ArrayList<TreeNode> r = dfs(k + 1, j);
			for (TreeNode left : l) {
				for (TreeNode right : r) {
					TreeNode root = new TreeNode(k);
					root.left = left;
					root.right = right;
					res.add(root);
				}
			}
		}
		return res;
	}
}
